//============================================================================
// Name        : GA.cpp
// Author      : Andrey Bicalho Santos e Clayson Sandro Celes
// Version     :
// Copyright   : Your copyright notice
// Description : Genetic Algorithm in C++, Ansi-style
//============================================================================
#include "GA.h"
#include <cstdlib>
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
using namespace std;

/*
 * default constructor
 * */
GA::GA(){
	current_age = 0;
	k_best_individuals_e =  NULL;
	k_best_index_t = NULL;
	max_min = true;
	srand(time(NULL));
}

/**/
GA::GA(int n_ag,int n_genes,int n_ind,int c_x,int c_y,int m_x, int m_y,int k_t,int k_e,int tipo){
	srand(time(NULL));
	current_age = 0;
	number_ages = n_ag;
	num_genes = n_genes;
	num_individuals_population = n_ind;
	crossover_rate_x = c_x;
	crossover_rate_y = c_y;
	mutation_rate_x = m_x;
	mutation_rate_y = m_y;
	k_from_tournament = k_t;
	k_best_individuals_for_elitism = k_e;

	k_best_index_t = new int[k_from_tournament];

	if(tipo == 0) max_min = false;
	else max_min = true;

	k_best_individuals_e = new Individual[k_best_individuals_for_elitism];
	for(int i=0;i<k_best_individuals_for_elitism;i++){
		k_best_individuals_e[i].setNumGenes(num_genes);
		k_best_individuals_e[i].Initialize();
	}

	dad.setNumGenes(num_genes);
	dad.Initialize();

	mom.setNumGenes(num_genes);
	mom.Initialize();

	child.setNumGenes(num_genes);
	child.Initialize();
}

/**/
void GA::pera(){
	string x;
	cin >> x;
}

/**/
void GA::InsertionSort(int A[],Individual pop[],int length){
	int i,j,tmp;
	for(i = 1;i < length;i++){
		j = i;
		while(j > 0 && pop[A[j-1]].getFitness() > pop[A[j]].getFitness()){
			tmp = A[j];
			A[j] = A[j-1];
			A[j-1] = tmp;
			j--;
		}
	}
}

/**/
void GA::setAge(int n){
	number_ages = n;
}

/**/
int GA::getAge(){
	return number_ages;
}

/**/
int GA::getCurrentAge(){
	return current_age;
}

/**/
void GA::setKfromTournamentParameter(int k){
	k_from_tournament = k;
}

/**/
int GA::getKfromTournamentParameter(){
	return k_from_tournament;
}

/**/
int GA::getKBestIndividualsForElitismParameter(){
	return k_best_individuals_for_elitism;
}

/**/
void GA::setKBestIndividualsForElitismParameter(int k){
	k_best_individuals_for_elitism = k;
}

/**/
void GA::setCrossOverType(int t){
	if(t > 3 || t < 1)
		cout << "Invalid Crossover type, please select a valid one: \n1 - One-Point Crossover\n2 - Two-Points Crossover\n3 - Uniform Crossover\n";
	else crossover_type = t;
}

/**/
int GA::getCrossOverType(){
	return crossover_type;
}


/**/
void GA::setMutationRate(int m_rate_x,int m_rate_y){
	mutation_rate_x = m_rate_x;
	mutation_rate_y = m_rate_y;
}

/**/
int *GA::getMutationRate(){
	mutation_rate = new int[2];
	mutation_rate[0] = mutation_rate_x;
	mutation_rate[1] = mutation_rate_y;

	return mutation_rate;
}

/**/
void GA::setCrossOverRate(int c_rate_x,int c_rate_y){
	crossover_rate_x = c_rate_x;
	crossover_rate_y = c_rate_y;
}

/**/
int *GA::getCrossOverRate(){
	int *c;
	c = new int[2];
	c[0] = crossover_rate_x;
	c[1] = crossover_rate_y;

	return c;
}

/**/
void GA::setNumIndividuals(int n_ind){
	num_individuals_population = n_ind;
}

/**/
int GA::getNumIndividuals(){
	return num_individuals_population;
}


/**/
int GA::getHighestFitnessIndividualIndex(Individual *population){
	int *index_best_individual;

	index_best_individual = new int[num_individuals_population];
	for(int i=0;i<num_individuals_population;i++)
		index_best_individual[i] = i;

	InsertionSort(index_best_individual,population,num_individuals_population);

	int melhor = index_best_individual[num_individuals_population-1];

	delete[] index_best_individual;
	return melhor;
}

/**/
int GA::getLowestFitnessIndividualIndex(Individual *population){
	int *index_best_individual;

	index_best_individual = new int[num_individuals_population];
	for(int i=0;i<num_individuals_population;i++)
		index_best_individual[i] = i;

	InsertionSort(index_best_individual,population,num_individuals_population);

	int melhor = index_best_individual[0];

	delete[] index_best_individual;
	return melhor;
}


/**/
void GA::printPopulation(Individual *population){
	for(int i=0;i<num_individuals_population;i++)
		population[i].printIndividual();
}

/**/
void GA::printFitnessPopulation(Individual *population){
	for(int i=0;i<num_individuals_population;i++)
		population[i].printFitnessIndividual();
}

/**/
double GA::getAverageFitness(Individual *population){
	double avg_fit = 0;
	for(int i=0;i<num_individuals_population;i++){
		avg_fit += population[i].getFitness();
	}

	return avg_fit/num_individuals_population;
}

/**/
double GA::getStdDevFitness(Individual *population){
	double stddev = getVarianceFitness(population);

	return sqrt(stddev);
}

/**/
double GA::getVarianceFitness(Individual *population){
	double average = getAverageFitness(population);
	double variance = 0;

	for(int i=0;i<num_individuals_population;i++)
		variance += pow((population[i].getFitness() - average),2);

	variance = variance/(num_individuals_population-1);

	return variance;
}

/*
 * usage:
 * 	Tournament(population,&ind);
 * tournament with subset of size k
 * individuals are ordered according to its fitness using InsertionSort algorithm
 * max_min controls maximization or minimization fitness
 * set it true for maximization
 * set it false for minimization
 * */
void GA::TournamentSelection(Individual *pop,Individual *ind){

	for(int i=0;i<k_from_tournament;i++)
		k_best_index_t[i] = rand() % num_individuals_population;


	InsertionSort(k_best_index_t,pop,k_from_tournament);

	if(max_min){
		//return pop[k_best_index_t[k_from_tournament-1]]; // chama destrutor... portanto...
		ind->setNumGenes(pop[k_best_index_t[k_from_tournament-1]].getNumGenes());
		ind->ReInitialize();
		ind->setFitness(pop[k_best_index_t[k_from_tournament-1]].getFitness());
		ind->setChromosome(pop[k_best_index_t[k_from_tournament-1]].getChromosome());
	}
	else{
		//return pop[k_best_index_t[0]]; //chama destrutor.... portanto essa funcao nao tera retorno mais... ind sera alterado por referencia
		ind->setNumGenes(pop[0].getNumGenes());
		ind->ReInitialize();
		ind->setFitness(pop[k_best_index_t[0]].getFitness());
		ind->setChromosome(pop[k_best_index_t[0]].getChromosome());

	}

}

void GA::OnePointCrossOver(Individual *dad_, Individual *mom_,Individual *child_){

}

void GA::TwoPointsCrossOver(Individual *dad_, Individual *mom_,Individual *child_){

}

/*
 * usage:
 * 	UniformCrossOver(&dad,&mom,&child);
 * uniform crossover of probability of 50% to select each parent
 * */
void GA::UniformCrossOver(Individual *dad_, Individual *mom_,Individual *child_){
		//time_t t;
		//srand((unsigned) time(&t));

		/*
		 //abordagem 1
		//num de genes do filho = (num de genes do pai + num de genes da mae) dividido por dois ..... media
	    //os genes "extras" serao alocados por um processo aleatorio
		int point, media_genes,menor_num_genes;

		if(dad_->getNumGenes() >= mom_->getNumGenes())
			menor_num_genes = mom_->getNumGenes();
		else menor_num_genes = dad_->getNumGenes();

		media_genes = (dad_->getNumGenes() + mom_->getNumGenes())/2;

		child_->setNumGenes(media_genes);
		child_->ReInitialize();

		for(int i=0;i<child_->getNumGenes();i++){
			if(i < menor_num_genes){
				point = rand() % 2;

				if(point == 0) child_->setGene(i,dad_->getGene(i));
				else child_->setGene(i,mom_->getGene(i));
			}
			else{ //processo aleatorio ... nao serao genes nem do pai nem da mae...
				if(rand() % 100 < 50) child_->setGene(i,0);
				else child_->setGene(i,1);
			}
		}
		 */


		//abordagem 2
	    //filho tera tamanho igual ao melhor pai (baseado na fitness)
		/*int point;

		if(dad_->getFitness() >= mom_->getFitness())
			child_->setNumGenes(dad_->getNumGenes());
		else child_->setNumGenes(mom_->getNumGenes());

		child_->ReInitialize();

		for(int i=0;i<child_->getNumGenes();i++){
			if(i < dad_->getNumGenes() && i < mom_->getNumGenes()){ //faz uniform crossover
				point = rand() % 2;
				if(point == 0) child_->setGene(i,dad_->getGene(i));
				else child_->setGene(i,mom_->getGene(i));
			}
			else if(i >= dad_->getNumGenes()){ //pega genes da mae
				child_->setGene(i,mom_->getGene(i));
			}
			else{
				child_->setGene(i,dad_->getGene(i)); //pega genes do pai
			}

		}*/


		/*
		//abordagem 3
		//filho tera o tamanho do menor pai
		if(dad_->getNumGenes() <= mom_->getNumGenes()){
			child_->setNumGenes(dad_->getNumGenes());
			child_->ReInitialize();
			for(int i=0;i<child_->getNumGenes();i++){
				point = rand() % 2;

				if(point == 0)
					child_->setGene(i,dad_->getGene(i));
				else
					child_->setGene(i,mom_->getGene(i));
			}

		}
		else{
			child_->setNumGenes(mom_->getNumGenes());
			child_->ReInitialize();
			for(int i=0;i<child_->getNumGenes();i++){
				point = rand() % 2;

				if(point == 0)
					child_->setGene(i,dad_->getGene(i));
				else
					child_->setGene(i,mom_->getGene(i));
			}

		}*/

		//return child; //nao há a necessidade do retorno poois child é alterado por referencia...
						//alem disso o destrutor da classe individual iria ser chamado para os objetos recebidos

	//abordagem 4 baseada na 2

	int point;

	if(rand() % 100 <= 50)
		child_->setNumGenes(dad_->getNumGenes());
	else child_->setNumGenes(mom_->getNumGenes());


	child_->ReInitialize();

	for(int i=0;i<child_->getNumGenes();i++){
		if(i < dad_->getNumGenes() && i < mom_->getNumGenes()){ //faz uniform crossover
			point = rand() % 2;
			if(point == 0) child_->setGene(i,dad_->getGene(i));
			else child_->setGene(i,mom_->getGene(i));
		}
		else if(i >= dad_->getNumGenes()){ //pega genes da mae
			child_->setGene(i,mom_->getGene(i));
		}
		else{
			child_->setGene(i,dad_->getGene(i)); //pega genes do pai
		}

	}

}

/**/
void GA::Mutation(Individual *ind){

	int mutation_probability;

	for(int i=0;i<ind->getNumGenes();i++){
		mutation_probability = rand() % mutation_rate_x;
		if(mutation_probability <= mutation_rate_y){ //printf("\nOcorreu Mutacao!\n");
			if(ind->getGene(i) == 1) ind->setGene(i,0);
			else ind->setGene(i,1);
		}
	}

}

/**/
void GA::Elitism(Individual *old_pop,Individual *new_pop, Individual *k_best_elitism){

	int index_best_individual;

	if(max_min){
		for(int i=0;i<k_best_individuals_for_elitism;i++){
			index_best_individual = getHighestFitnessIndividualIndex(old_pop);
			k_best_elitism[i].setNumGenes(old_pop[index_best_individual].getNumGenes());
			k_best_elitism[i].ReInitialize();
			k_best_elitism[i].setFitness(old_pop[index_best_individual].getFitness());
			k_best_elitism[i].setChromosome(old_pop[index_best_individual].getChromosome());
			old_pop[index_best_individual].setFitness(-1000000000); //arruinando a vida do individuo p nao ser escolhido novamente...
		}
	}
	else{
		for(int i=0;i<k_best_individuals_for_elitism;i++){
			index_best_individual = getLowestFitnessIndividualIndex(old_pop);
			k_best_elitism[i].setNumGenes(old_pop[index_best_individual].getNumGenes());
			k_best_elitism[i].ReInitialize();
			k_best_elitism[i].setFitness(old_pop[index_best_individual].getFitness());
			k_best_elitism[i].setChromosome(old_pop[index_best_individual].getChromosome());
			old_pop[index_best_individual].setFitness(1000000000); //arruinando a vida do individuo p nao ser escolhido novamente...
		}
	}

	//printf("\noi 1\n"); pera();
	int cont = 0;
	for(int i=(num_individuals_population-k_best_individuals_for_elitism);i<num_individuals_population;i++){
		new_pop[i].setNumGenes(k_best_elitism[cont].getNumGenes());
		new_pop[i].Initialize();
		new_pop[i].setFitness(k_best_elitism[cont].getFitness());
		new_pop[i].setChromosome(k_best_elitism[cont].getChromosome());
		//k_best_elitism[cont].printIndividual(); pera();
		cont++;
	}

}

/**/
Individual *GA::Run(Individual *population){

	//printPopulation(population); pera();

	Individual *new_population;

	new_population = new Individual[num_individuals_population];

	//printf("\nantes das operacoes\n"); printPopulation(population);  pera();

	int crossover_probability;

	if(k_best_individuals_for_elitism > 0){

		for(int i=0;i<(num_individuals_population-k_best_individuals_for_elitism);i++){
			crossover_probability = rand() % crossover_rate_x;
			if (crossover_probability <= crossover_rate_y) {
				TournamentSelection(population, &dad);
				TournamentSelection(population, &mom);
				//printf("\ndad:");dad.printIndividual();
				//printf("\nmom:");mom.printIndividual();
				UniformCrossOver(&dad, &mom, &child);
				Mutation(&child);
				//printf("\nchild:"); child.printIndividual(); pera();

				//new_population[i].setFitness(child.getFitness());
				//new_population[i].setChromosome(child.getChromosome());

				new_population[i].setNumGenes(child.getNumGenes());
				new_population[i].Initialize();
				new_population[i].setFitness(child.getFitness());
				new_population[i].setChromosome(child.getChromosome());

				//printf("\nnovo individuo na populacao:"); new_population[i].printIndividual(); pera();
				//printPopulation(population); pera();
			}
			else{
				new_population[i].setNumGenes(population[i].getNumGenes());
				new_population[i].Initialize();
				new_population[i].setFitness(population[i].getFitness());
				new_population[i].setChromosome(population[i].getChromosome());
			}

		}

		Elitism(population,new_population,k_best_individuals_e);
		//printPopulation(new_population); pera();


	}
	else{
		for(int i=0;i<num_individuals_population;i++){
			crossover_probability = rand() % crossover_rate_x;
			if (crossover_probability <= crossover_rate_y) {
				TournamentSelection(population, &dad);
				TournamentSelection(population, &mom);
				//printf("\ndad:");dad.printIndividual();
				//printf("\nmom:");mom.printIndividual();
				UniformCrossOver(&dad, &mom, &child);
				Mutation(&child);
				//printf("\nchild:"); child.printIndividual(); pera();

				//new_population[i].setFitness(child.getFitness());
				//new_population[i].setChromosome(child.getChromosome());

				new_population[i].setNumGenes(child.getNumGenes());
				new_population[i].Initialize();
				new_population[i].setFitness(child.getFitness());
				new_population[i].setChromosome(child.getChromosome());

				//printf("\nnovo individuo na populacao:"); new_population[i].printIndividual(); pera();
				//printPopulation(population); pera();
			}
			else{
				new_population[i].setNumGenes(population[i].getNumGenes());
				new_population[i].Initialize();
				new_population[i].setFitness(population[i].getFitness());
				new_population[i].setChromosome(population[i].getChromosome());
			}
		}

		//printf("\ndepois das operacoes\n"); printPopulation(new_population); pera();
	}



	delete[] population;

	current_age++;
	//printPopulation(new_population); pera();

	return new_population;

}

/**/
GA::~GA(){
	if(k_best_index_t) delete[] k_best_index_t;
	if(mutation_rate) delete[] mutation_rate;
	if(k_best_individuals_e) delete[] k_best_individuals_e;

}
